﻿//https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    //顺时针方向的旋转 和各个方向上的移动
    int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        if (matrix.size() == 0 || matrix[0].size() == 0)
        {
            return {};
        }

        int n = matrix.size(), m = matrix[0].size();
        vector<vector<bool>> vist(n, vector<bool>(m));
        int total = n * m;
        vector<int> ret(total);

        int row = 0, col = 0, dirIndex = 0;
        for (int i = 0; i < total; i++)
        {
            //将当前位置的值加入结果
            ret[i] = matrix[row][col];
            vist[row][col] = true;
            //走向下一个位置
            int newrow = row + dir[dirIndex][0], newcol = col + dir[dirIndex][1];
            //判断下一个位置是否越界以及是否被访问过
            if (newrow < 0 || newrow >= n || newcol < 0 || newcol >= m || vist[newrow][newcol])
            {
                //顺时针方向旋转位置
                dirIndex = (dirIndex + 1) % 4;
            }
            //更新越界前的最后一个位置的下一个位置
            row += dir[dirIndex][0];
            col += dir[dirIndex][1];
        }

        return ret;
    }
};